500 MB Nyheder Direkte fra Internet 2/500 MB nyheder direkte fra internet CD 2.iso/start/data/text/numeric.txt

Text File | 1994-09-21 | 14KB | 419 lines

                     ERRORS
  Computers make mathematical errors. Here's why.

     Twin problems that confuse the computer
  Look at this pair of problems. . . .
Problem 1: solve the equation x²-4x+4 = 0.
Problem 2: solve the equation x²-4x+3.9999999 = 0.
Those two problems resemble each other. The only difference is
that where the second problem says 3.9999999, the first problem
says 4. But the correct solutions to the problems are quite
different from each other:
The correct solution to problem 1 is ``x = 2''.
The correct solution to problem 2 is "x = 1.9996838 or x =
2.0003162".
  Unfortunately, problem 1 looks so similar to problem 2 that the
computer can hardly tell the difference. Some computers treat
3.9999999 as if it were 4. If you ask such a computer to solve
problem 2, it will solve problem 1 instead, and its answer to
problem 2 will therefore be wrong.
  Here's another pair of problems. . . .
Problem 3: solve the equation (x-1)*(x-2)*(x-3)*(x-4)*...*(x-20)
= 0.

Problem 4: solve the equation (x-1)*(x-2)*(x-3)*(x-4)*...*(x-20)
-2-23*x19 = 0.
Those two problems resemble each other. In fact, if you ``expand
the polynomial'', you'll see that problem 3 can be rewritten like
this:
x20 - 210x19 + ... = 0.
Problem 4 can be rewritten like this:
x20 - (210+2-23)x19 + ... = 0.
So problem 4 differs from problem 3 just by saying 210+2-23
instead of 210. Since 2-23 is a tiny number (approximately
.0000001), some computers can't tell the difference between 210
and 210+2-23, can't distinguish problem 4 from problem 3, and say
the same answer to problem 4 as to problem 3. But the correct
solutions to the two problems are different:
The correct solution to problem 3 is ``x=1 or x=2 or x=3 or x=4
or ... or x=20''.

The correct solution to problem 4 is ``x=1.000 or x=2.000 or
x=3.000 or x=4.000 or x=5.000 or x=6.000 or x=7.000 or x=8.007 or
x=8.917 or x=10.095±.644i or x=11.794±1.652i or x=13.992±1.519i
or x=16.731±2.813i or x=19.502±1.940i or x=20.847''. (i denotes
the square root of -1.)
  Here's one more case. . . .
Problem 5: solve the simultaneous equations ``913x+659y=254 and
780x+563y=217''.
Problem 6: solve the simultaneous equations ``913x+659y=254 and
780x+563y=216.999''.
Although the problems are almost identical (so that some
computers can't distinguish them from each other), the correct
solutions are quite different:
The correct solution to problem 5 is ``x=1    and y=-1''.
The correct solution to problem 6 is ``x=.341 and y=-.087''.
  That last case of ``confusing twins'' leads to this fascinating
paradox. . . . Suppose you tell your friendly computer to
``guess'' an x and y to solve problem 5:
913x + 659y = 254
780x + 563y = 217
If the computer guesses ``x=.999 and y=-1.001'', it finds:
913x + 659y = 252.428
780x + 563y = 215.757
But if the computer guesses ``x=.341 and y=-.087'' instead, it
finds:
913x + 659y = 254
780x + 563y = 216.999, which is about 217
The computer therefore deduces that its second guess is almost
perfect and much better than its first guess. But ___ here's the
paradox ___ the second guess is not
better than the first guess; the first guess is better, because
the correct solution is ``x=1 and y=-1'', which is closer to the
first guess.

                                                    Reduce round-off error
                                                     By the laws
of mathematics, 5+.14+.14+.14 should be the same as
.14+.14+.14+5. But a calculator that holds just two significant
digits gives different answers:
5+.14+.14+.14              .14+.14+.14+5

    5.0                         .14
    +.14                       +.14
    5.1                         .28
    +.14                       +.14
    5.2                         .42
    +.14                      +5.0
    5.3                        5.4
Since the correct answer is 5.42, the calculation on the right is
more accurate. The general rule is: when adding a list of
numbers, you'll get more accuracy if you begin with the numbers
closest to 0. The rule is valid even on a top-quality computer,
although the computer's inaccuracies are not so obvious.
                                                     By the laws
of mathematics, (31/5 - 31/7)*70 is 4:
  1     7
 3  = 3
  5    35


  1     5
-3  = 3
  7    35

        2
          * 70 = 4
       35
But if we try that calculation on our two-digit calculator, we
get a totally different answer:
  1
 3  = 3+.2  = 3.2
  5


  1
-3  = 3+.14 = 3.1
  7
               .1 * 70 = 7.0
The general warning is: when you subtract two numbers that are
almost equal (like 31/5 and 31/7), few of the digits in your
answer will be correct. The warning is valid even on a
top-quality computer, although the computer's inaccuracies are
not so obvious.

              ESTIMATES
  The computer can estimate an answer.

         Connecting the dots
  Suppose you're given the value of y when x is 1, 2, 3, 4, and
5:
Suppose you'd like to make an ``intelligent guess'' as to the
value of y when x is 1.5, 3.01, 100, -400, and other values.
Guessing y for an in-between x (such as 1.5 and 3.01) is called
interpolation; guessing y for a very large x or a very small x
(such as 100 and -400) is called extrapolation.
  One way to guess is to connect the points with line segments:
That's called piecewise linear estimation.
  You get a much smoother picture by using a cubic spline:
P1 and P6 are parts of straight lines. P2, P3, P4, and P5 are
parts of four different cubics (third-degree polynomials), chosen
so that, at the point where Pi meets Pi+1, Pi has the same
derivative and second derivative as Pi+1. (The term
``derivative'' is defined by calculus.)
                                                 Least-square line
                                         Suppose you're given
these approximate values of y:
To estimate y for other values of x, you could use piecewise
linear estimation or a cubic spline. But notice the points lie
almost on a straight line:
The points aren't exactly on that line; the errors in the y
values are e1, e2, e3, e4, and e5. The line's squared error is
e1² + e2² + e3² + e4² + e5². This line has a larger squared
error:
The line having the smallest squared error is called the
least-square line, and is considered to be the line that best
approximates the data.

           SOLVE EQUATIONS
  The computer can solve equations.

          Single equations
  Suppose you want to solve a tough equation, such as 2x+x3=20.
Rewrite it to make the right side be 0:
2x+x3-20=0
Let f(x) denote the left side of the equation:
f(x) is 2x+x3-20
So the equation you want to solve is f(x)=0. Here's a way to
solve it ___ called the secant method. . . .
  Let x1 and x2 be your favorite numbers. Graph f(x1) and f(x2):
Let x3 be where the line connecting those points hits the x axis:
Graph f(x3); it's probably close to 0:
Connect the x2 point to the x3 point, to find x4:
Connect the x3 point to the x4 point, to find x5:
Probably you'll get closer and closer to the point where f(x) is
0.
  A different method, called Muller's method, uses parabolas
instead of straight lines. . . .
                                         Let x1, x2, and x3 be
your three favorite numbers. A common choice is -.5, .5, and 0.
Graph f(x1), f(x2), and f(x3):
Draw the parabola that passes through those points:
The parabola hits the x axis at two points (although the points
might be what mathematicians call "imaginary"). Let x4 be at one
of those points. For best results, choose the point that's closer
to the origin:
Graph f(x4):
Draw a parabola through the x2, x3, and x4 points, to find x5:
Probably you'll get closer to the place where f(x) is 0.
                                         Usually, Muller's method
moves toward the solution more rapidly than the secant method. It
can even find complex, ``non-real'' solutions, since the x value
where the parabola hits the x axis might be of the form a+bi,
where i denotes the square root of -1. (If you're interested in
just solutions that are real, pretend b is 0.)
                                         Using either the secant
method or Muller's, suppose you finally find a solution of the
equation 2x+x3-20=0. Let s1 denote that solution. To hunt for
additional solutions, try solving this equation:
 x  3
2 +x -20
         = 0
  x-s
     1
If you find a solution of that new equation, call it s2, and
solve this equation:
   x  3
  2 +x -20
             = 0
(x-s )(x-s )
    1     2
If that produces a solution s3, solve
      x  3
     2 +x -20
                   = 0
(x-s )(x-s )(x-s )
    1     2     3
to find s4. The solutions s1, s2, s3, s4, etc., are all solutions
of the original equation.
  The round-off error will be less if |s1| < |s2| < |s3| < |s4| <
.... So when you hunt for solutions, begin by trying to find the
solutions closest to zero. That's why, when Muller's parabola
hits the x axis in two points, you should pick the point that's
closer to zero. And that's why a common choice for x1, x2, and x3
is numbers near zero.

       Simultaneous equations
  Try to solve these simultaneous linear equations:
8x +  y -  z =  8
2x +  y + 9z = 12
 x - 7y + 2z = -4
  An obvious way is Gauss-Jordan elimination. Eliminate the first
coefficient:
     1    1                             1
 x +  y -  z =  1      (I multiplied by  )
     8    8                             8

2x +  y + 9z = 12

 x - 7y + 2z = -4
Eliminate everything below it:
     1    1
 x +  y -  z =  1
     8    8

     3   37
      y +  z = 10      (I subtracted twice the first row)
     4    4

    57   17
   -  y +  z = -5      (I subtracted the first row)
     8    8
Eliminate the first coefficient in the second row:
     1    1
 x +  y -  z =  1
     8    8

         37    40                       4
      y +  z =         (I multiplied by  )
          3     3                       3

    57   17
   -  y +  z = -5
     8    8
Eliminate everything above and below it:
          5     2                    1
 x      -  z = -       (I subtracted   times the second row)
          3     3                    8

         37    40
      y +  z =
          3     3

                                57
         90z = 90      (I added    times the second row)
                                 8
Eliminate the first coefficient in the third row:
          5     2
 x      -  z = -
          3     3

         37    40
      y +  z =
          3     3

                                         1
           z = 1       (I multiplied by   )
                                        90
Eliminate everything above it:
                                5
 x           = 1       (I added   times the third row)
                                3

                                     37
      y      = 1       (I subtracted    times the third row)
                                      3

           z = 1
That's the solution. (It's depressing that so much computation
was needed, to get such a simple solution!)
  In that example, I pivoted on the first coefficient of the
first equation, then the first coefficient of the second
equation, and finally the first coefficient of the third
equation. To reduce the computer's round-off error, it's better
at each stage to pivot on the coefficient that has the largest
absolute value, relative to the coefficients in its row. For
example, at this stage ___
     1    1
 x +  y -  z =  1
     8    8

     3   37
      y +  z = 10
     4    4

    57   17
   -  y +  z = -5
     8    8
it would have been better to pivot on -57/8 than on 3/4,  since
57/8 divided by 17/8 is bigger than 3/4 divided by 37/4.
                                         Now let's go back to the
original equations ___
8x +  y -  z =  8
2x +  y + 9z = 12
 x - 7y + 2z = -4
and solve them by a different method, called Gauss-Seidel
iteration. In each equation, find the variable whose coefficient
has the largest absolute value, and put that variable on one
side:
     1    1
x = - y +  z + 1
     8    8

     2    1    4
z = - x -  y +
     9    9    3

     1    2    4
y =   x +  z +
     7    7    7
Begin by guessing that x, y, and z are all 0, then improve the
guesses by using those equations. Here are the calculations, to
three decimal places:
x = 0
y = 0
z = 0
     1    1
x = - y +  z + 1 = 1.000
     8    8

     1    2    4
y =   x +  z +   =  .714
     7    7    7

     2    1    4
z = - x -  y +   = 1.032
     9    9    3

     1    1
x = - y +  z + 1 = 1.041
     8    8

     1    2    4
y =   x +  z +   = 1.014
     7    7    7

     2    1    4
z = - x -  y +   =  .990
     9    9    3

     1    1
x = - y +  z + 1 =  .997
     8    8

     1    2    4
y =   x +  z +   =  .996
     7    7    7

     2    1    4
z = - x -  y +   = 1.002
     9    9    3

     1    1
x = - y +  z + 1 = 1.001
     8    8

     1    2    4
y =   x +  z +   = 1.000
     7    7    7

     2    1    4
z = - x -  y +   = 1.000
     9    9    3

     1    1
x = - y +  z + 1 = 1.000
     8    8

     1    2    4
y =   x +  z +   = 1.000
     7    7    7

     2    1    4
z = - x -  y +   = 1.000
     9    9    3
In the example, x and y and z gradually approach the correct
solutions.
                                         Is Gauss-Seidel
iteration better or worse than Gauss-Jordan elimination?
                                         A disadvantage of
Gauss-Seidel iteration is: it doesn't guarantee you'll approach
the correct solution. If you follow the advice about pivoting on
the coefficient that has the largest relative absolute value, you
stand a better chance of approaching the correct solution, but
there's no guarantee.
                                         On the other hand, if
Gauss-Seidel iteration does approach a solution, the solution
will have less round-off error than with Gauss-Jordan
elimination.